package com.zhangx.datastructure.graph;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 邻接表
 * 关心了出度
 * 还有逆邻接表-关心入度
 * 两者结合十字链表都解决了，但是结构还是比较复杂
 * P228
 *
 * 数组+链表
 */
public class ALGraph {
    int MAXVEX = 5;
    VertexNode[] adjList = new VertexNode[MAXVEX];
    int numVertexes;//顶点数
    int numEdges;//边数
    boolean visited[];
    /**
     * 顶点
     */
    class VertexNode{
        String data;
        EdgeNode firstEdge;

        public VertexNode(String data){
            this.data = data;
        }

        @Override
        public String toString() {
            return "VertexNode{" +
                    "data='" + data + '\'' +
                    ", firstEdge=" + firstEdge +
                    '}';
        }
    }

    @Override
    public String toString() {
        for (int i = 0; i < adjList.length; i++) {
            System.out.println(adjList[i]);
        }
        return "ALGraph{" +
                "MAXVEX=" + MAXVEX +
                ", adjList=" + Arrays.toString(adjList) +
                ", numVertexes=" + numVertexes +
                ", numEdges=" + numEdges +
                '}';
    }

    /**
     * 构建了7-5-2的数据
     */
    public ALGraph(){
        numVertexes = 9;
        MAXVEX = 9;
        numEdges = 15;
        adjList = new VertexNode[MAXVEX];
        visited = new boolean[MAXVEX];
//        大写A
        short start = 65;
//        先构建顶点
        for (int i = 0; i < adjList.length; i++) {
            VertexNode vertexNode = new VertexNode(Character.toString((char)start));
            start++;
            adjList[i] = vertexNode;
        }
//        A-0,B-1,C-2,D-3,E-4,F-5,G-6,H-7,I-8
//        A的出度 B(1) F(5)
        VertexNode a = adjList[0];
        EdgeNode af = new EdgeNode(5,null);
        EdgeNode ab = new EdgeNode(1,af);
        a.firstEdge = ab;

        VertexNode b = adjList[1];
//        c-2,i-8,g-6
        EdgeNode bg = new EdgeNode(6,null);
        EdgeNode bi = new EdgeNode(8,bg);
        EdgeNode bc = new EdgeNode(2,bi);
        b.firstEdge = bc;

        VertexNode c = adjList[2];
//        cb ci cd
        EdgeNode c_ = new EdgeNode(getIndex('B'),
                new EdgeNode(getIndex('D'),
                        new EdgeNode(getIndex('I'),null)));
        c.firstEdge = c_;

        VertexNode d = adjList[3];
//        dc de  dg dh di
        EdgeNode d_ = new EdgeNode(getIndex('C'),
                new EdgeNode(getIndex('E'),
                        new EdgeNode(getIndex('G'),
                                new EdgeNode(getIndex('H'),
                                        new EdgeNode(getIndex('I'),null)))));
        d.firstEdge = d_;

        VertexNode e = adjList[4];
//        ed ef eh
        EdgeNode e_ = new EdgeNode(getIndex('D'),
                new EdgeNode(getIndex('F'),
                        new EdgeNode(getIndex('H'),null)));
        e.firstEdge = e_;

        VertexNode f = adjList[5];
//        fa fe fg
        EdgeNode f_ = new EdgeNode(getIndex('A'),
                new EdgeNode(getIndex('E'),
                        new EdgeNode(getIndex('G'),null)));
        f.firstEdge = f_;

        VertexNode g = adjList[6];
//        gb gd gf gh
        EdgeNode g_ = new EdgeNode(getIndex('B'),
                new EdgeNode(getIndex('D'),
                        new EdgeNode(getIndex('F'),
                                new EdgeNode(getIndex('H'),null))));
        g.firstEdge = g_;

        VertexNode h = adjList[7];
//        hd he hf hg
        EdgeNode h_ = new EdgeNode(getIndex('D'),
                new EdgeNode(getIndex('E'),
                        new EdgeNode(getIndex('F'),
                                new EdgeNode(getIndex('G'),null))));
        h.firstEdge = h_;


        VertexNode i = adjList[8];
//        IB IC ID
        EdgeNode i_ = new EdgeNode(getIndex('B'),
                new EdgeNode(getIndex('C'),
                        new EdgeNode(getIndex('D'),null)));
        i.firstEdge = i_;
    }

    private int getIndex(char c){
        return ((short)c) - 65;
    }


    /**
     * 边表节点,顶点的出度
     */
    class EdgeNode{
        int weight;
        int adjvex;//在顶点数组中的下标
        EdgeNode next;

        public EdgeNode(int adjvex,EdgeNode next){
            this.adjvex = adjvex;
            this.next = next;
        }

        @Override
        public String toString() {
            return "EdgeNode{" +
                    "weight=" + weight +
                    ", adjvex=" + adjvex +
                    ", next=" + next +
                    '}';
        }
    }

    /**
     * 深度优先递归
     * @param i
     */
    public void DFS(int i){
        visited[i] = true;
        System.out.println(adjList[i].data);
        EdgeNode edgeNode = adjList[i].firstEdge;
        while (edgeNode!=null){
            if(!visited[edgeNode.adjvex]){
//                如果这节点没被访问到，递归
                DFS(edgeNode.adjvex);
            }
            edgeNode = edgeNode.next;
        }
    }

    /**
     * 深度遍历操作
     */
    void DFSTraverse(){
//        全初始化为未访问状态
        for (int i = 0; i < numVertexes; i++) {
            visited[i] = false;
        }
        for (int i = 0; i < numVertexes; i++) {
            if (!visited[i]){
//                实际只会一次，因为递归后就变成访问状态了
                System.out.println("因为"+i+"节点未访问，开始递归");
                DFS(i);
            }
        }

    }

    /**
     * 广度遍历
     */
    void BFSTraverse(){
//        全初始化为未访问状态
        for (int i = 0; i < numVertexes; i++) {
            visited[i] = false;
        }
        int i = 0;
        EdgeNode p;
        Queue<Integer> q = new LinkedList<>();
        for (i = 0; i < numVertexes; i++) {
            if (!visited[i]){
                visited[i] = true;
                System.out.println(adjList[i].data);
                q.offer(i);
                while (!q.isEmpty()){
                    i = q.poll();
//                    找到vetx[i]的联通节点
                    p = adjList[i].firstEdge;
                    while (p!=null){
                        if(!visited[p.adjvex]){
                            visited[p.adjvex] = true;
                            System.out.println(adjList[p.adjvex].data);
                            q.offer(p.adjvex);
                        }
                        p = p.next;
                    }

                }
            }
        }

    }

    public static void main(String[] args) {
        ALGraph alGraph = new ALGraph();
//        System.out.println(alGraph);
//        alGraph.DFSTraverse();
        alGraph.BFSTraverse();
    }
}
